import Queue from '@/sources/Queue/useDcl';
import AVL, { AVLNode } from './index'
import Assert from '@/utils/assets'
import { Console } from 'console';
export const test = () => {
    const avl = new AVL();
    const assert = new Assert()
    // const arr = [10, 8, 12, 7, 9, 6] // LL
    // const arr = [10, 8, 12, 13, 14, 15] // LL
    // const arr = [19, 15, 26, 7, 17, 16] // LR
    // const arr = [10, 8, 20, 16, 23, 19] // LR
    // const arr = [5, 10, 11, 12, 13, 14, 15] // LR
    // const arr = [20, 8, 7, 6, 5, 4, 3] // LR
    const arr = [20, 8, 7, 6, 5, 4, 3] // LR
    avl.batchAdd(arr);
    print(avl)
    // avl.batchRemove([20, 8, 7])
    console.log(avl.getRoot())
    // print(avl)
}

/**
 * 打印二叉树
 * @param avl 
 */
export const print = <T>(avl: AVL<T>) => {
    // 是空的
    if (avl.isEmpty()) return;
    let root = avl.getRoot();
    const queue = new Queue<AVLNode<T>>();
    queue.enQueue(root!);
    let levelSize = 1,
        height = 0;
    const hInfo: Record<string, Array<AVLNode<T>>> = {
        l1: []
    }

    while (!queue.isEmpty()) {
        const node = queue.deQueue()!;
        levelSize--;
        if (node === root) {
            // str += `${node.value} \n`
            hInfo.l1.push(node!)
        }
        // parent = node;
        // 左节点
        if (node.left) {
            queue.enQueue(node.left)
        }
        // 右节点
        if (node.right) {
            queue.enQueue(node.right)
        }

        if (levelSize === 0) {
            // 该层已经访问过了
            // 此时在队列的都是下一层
            levelSize = queue.size();

            const tmp = height + 2;
            queue.forEach((ele) => {
                (hInfo['l' + (tmp)] || (hInfo['l' + (tmp)] = [])).push(ele!)
            })

            // 更新层数
            height++
        }
    }
    printavlTree(hInfo)
}


/**
 * 打印出二叉树
 * @param d 
 */
const printavlTree = (d: Record<string, any>) => {
    const keys = Object.keys(d),
        len = keys.length;
    // root偏移的距离
    const padLen = 8;

    // 记录层数
    let desc = 4;

    let str = ''

    for (let i = 0; i < len; i++) {
        const sub = d[keys[i]],
            len = sub.length;
        for (let j = 0; j < len; j++) {
            if (i === 0) {
                // 第一层
                sub[j].pad = padLen
                str += `${pad(padLen)}${sub[j].value}(${sub[j].fac()})_p[${sub[j].parent?.value || ''}]`
            } else {
                // debugger
                // 不是第一层 
                const node = sub[j];
                // if (node.value === 15) debugger
                if (node.isLeft()) {
                    // 是左孩子
                    if (j === 0) {
                        // 该层第一个孩子
                        str += `${pad(node.parent.pad - desc) + sub[j].value}(${sub[j].fac()})_p[${sub[j].parent.value}]`
                        node.pad = node.parent.pad - desc
                    } else {
                        // 上一个节点的pad
                        const tmp = sub[j - 1].pad + 8
                        str += `${pad(8) + sub[j].value}(${sub[j].fac()})_p[${sub[j].parent.value}]`
                        node.pad = tmp
                    }

                } else {
                    // 是右孩子
                    if (j === 0) {
                        // 该层的第一个孩子
                        str += `${pad(node.parent.pad + desc) + sub[j].value}(${sub[j].fac()})_p[${sub[j].parent.value}]`
                        node.pad = node.parent.pad + desc
                    } else {
                        // debugger
                        const tmp = sub[j - 1].pad + 8
                        str += `${pad(8) + sub[j].value}(${sub[j].fac()})_p[${sub[j].parent.value}]`
                        node.pad = tmp
                    }
                }
            }
        }
        str += '\n'
    }

    console.log(str);
    // console.log('偏移:', pad(padLen).length)


}


/**
 * 填空
 * @param level 
 */
const pad = (level: number) => {
    return ''.padEnd(level, ' ')
}